home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / wzun11sr.zip / UNIMPLOD.C < prev    next >
Text File  |  1991-09-27  |  10KB  |  380 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   unimplod.c
  4.  
  5.   The Imploding algorithm is actually a combination of two distinct algor-
  6.   ithms.  The first algorithm compresses repeated byte sequences using a
  7.   sliding dictionary.  The second algorithm is used to compress the encoding
  8.   of the sliding dictionary ouput, using multiple Shannon-Fano trees.
  9.  
  10.   ---------------------------------------------------------------------------*/
  11.  
  12.  
  13. #include "unzip.h"
  14.  
  15.  
  16. /***********************/
  17. /*  UnImplode Defines */
  18. /***********************/
  19.  
  20. #define LITVALS     256
  21. #define DISTVALS    64
  22. #define LENVALS     64
  23. #define MAXSF       LITVALS
  24.  
  25.  
  26.  
  27. /************************/
  28. /*  UnImplode Typedefs */
  29. /************************/
  30.  
  31. typedef struct sf_entry {
  32.     byte Value;
  33.     byte BitLength;
  34. } sf_entry;
  35.  
  36. typedef struct sf_tree {        /* a shannon-fano "tree" (table) */
  37.     sf_entry entry[MAXSF];
  38.     int entries;
  39.     int MaxLength;
  40. } sf_tree;
  41.  
  42. typedef struct sf_node {        /* node in a true shannon-fano tree */
  43.     UWORD left;                 /* 0 means leaf node */
  44.     UWORD right;                /*   or value if leaf node */
  45. } sf_node;
  46.  
  47.  
  48.  
  49. /********************************/
  50. /*  UnImplode Global Variables */
  51. /********************************/
  52.  
  53. /* s-f storage is shared with that used by other comp. methods */
  54.  
  55. sf_tree lit_tree;
  56. sf_tree length_tree;
  57. sf_tree distance_tree;
  58. sf_node *lit_nodes = (sf_node *) prefix_of;     /* 2*LITVALS nodes */
  59. #ifdef MACOS
  60. sf_node *length_nodes ;  /* 2*LENVALS nodes */
  61. sf_node *distance_nodes ;    /* 2*DISTVALS nodes */
  62. #else
  63. sf_node *length_nodes = (sf_node *) suffix_of;  /* 2*LENVALS nodes */
  64. sf_node *distance_nodes = (sf_node *) stack;    /* 2*DISTVALS nodes */
  65. #endif
  66. boolean lit_tree_present;
  67. boolean eightK_dictionary;
  68. int minimum_match_length;
  69. int dict_bits;
  70.  
  71.  
  72.  
  73. /*****************************************/
  74. /*  UnImplode Local Function Prototypes */
  75. /*****************************************/
  76.  
  77. static void LoadTrees __((void));
  78. static void LoadTree __((sf_tree * tree, int treesize, sf_node * nodes));
  79. static void ReadLengths __((sf_tree * tree));
  80. static void SortLengths __((sf_tree * tree));
  81. static void GenerateTrees __((sf_tree * tree, sf_node * nodes));
  82. static void ReadTree __((register sf_node * nodes, int *dest));
  83.  
  84.  
  85.  
  86.  
  87.  
  88. /**************************/
  89. /*  Function unImplode() */
  90. /**************************/
  91.  
  92. void unImplode()
  93.  /* expand imploded data */
  94. {
  95.     register int srcix;
  96.     register int Length;
  97.     register int limit;
  98.     int lout;
  99.     int Distance;
  100.  
  101.     LoadTrees();
  102.  
  103. #ifdef DEBUG
  104.     printf("\n");
  105. #endif
  106.     while ((!zipeof) && ((outpos + outcnt) < ucsize)) {
  107.         READBIT(1, lout);
  108.  
  109.         if (lout != 0) {        /* encoded data is literal data */
  110.             if (lit_tree_present) {     /* use Literal Shannon-Fano tree */
  111.                 ReadTree(lit_nodes, &lout);
  112. #ifdef DEBUG
  113.                 printf("lit=%d\n", lout);
  114. #endif
  115.             } else
  116.                 READBIT(8, lout);
  117.  
  118.             OUTB(lout);
  119.         } else {                /* encoded data is sliding dictionary match */
  120.             READBIT(dict_bits, Distance);
  121.  
  122.             ReadTree(distance_nodes, &lout);
  123. #ifdef DEBUG
  124.             printf("d=%5d (%2d,%3d)", (lout << dict_bits) | Distance, lout,
  125.                    Distance);
  126. #endif
  127.             Distance |= (lout << dict_bits);
  128.             /* using the Distance Shannon-Fano tree, read and decode the
  129.                upper 6 bits of the Distance value */
  130.  
  131.             ReadTree(length_nodes, &lout);
  132.             Length = lout;
  133. #ifdef DEBUG
  134.             printf("\tl=%3d\n", Length);
  135. #endif
  136.             /* using the Length Shannon-Fano tree, read and decode the
  137.                Length value */
  138.  
  139.             if (Length == 63) {
  140.                 READBIT(8, lout);
  141.                 Length += lout;
  142.             }
  143.             Length += minimum_match_length;
  144.  
  145.             /* move backwards Distance+1 bytes in the output stream, and copy
  146.               Length characters from this position to the output stream.
  147.               (if this position is before the start of the output stream,
  148.               then assume that all the data before the start of the output
  149.               stream is filled with zeros.  Requires initializing outbuf
  150.               for each file.) */
  151.  
  152.             srcix = (outcnt - (Distance + 1)) & (OUTBUFSIZ - 1);
  153.             limit = OUTBUFSIZ - Length;
  154.             if ((srcix <= limit) && (outcnt < limit)) {
  155.                 outcnt += Length;
  156.                 while (Length--)
  157.                     *outptr++ = outbuf[srcix++];
  158.             } else {
  159.                 while (Length--) {
  160.                     OUTB(outbuf[srcix++]);
  161.                     srcix &= OUTBUFSIZ - 1;
  162.                 }
  163.             }
  164.         }
  165.     }
  166. }
  167.  
  168.  
  169.  
  170.  
  171.  
  172. /**************************/
  173. /*  Function LoadTrees() */
  174. /**************************/
  175.  
  176. static void LoadTrees()
  177. {
  178.     eightK_dictionary = (lrec.general_purpose_bit_flag & 0x02) != 0;    /* bit 1 */
  179.     lit_tree_present = (lrec.general_purpose_bit_flag & 0x04) != 0;     /* bit 2 */
  180.  
  181.     if (eightK_dictionary)
  182.         dict_bits = 7;
  183.     else
  184.         dict_bits = 6;
  185.  
  186.     if (lit_tree_present) {
  187.         minimum_match_length = 3;
  188.         LoadTree(&lit_tree, 256, lit_nodes);
  189.     } else
  190.         minimum_match_length = 2;
  191.  
  192.     LoadTree(&length_tree, 64, length_nodes);
  193.     LoadTree(&distance_tree, 64, distance_nodes);
  194. }
  195.  
  196.  
  197.  
  198.  
  199.  
  200. /*************************/
  201. /*  Function LoadTree() */
  202. /*************************/
  203.  
  204. static void LoadTree(tree, treesize, nodes)
  205. sf_tree *tree;
  206. int treesize;
  207. sf_node *nodes;
  208.  /* allocate and load a shannon-fano tree from the compressed file */
  209. {
  210.     tree->entries = treesize;
  211.     ReadLengths(tree);
  212.     SortLengths(tree);
  213.     GenerateTrees(tree, nodes);
  214. }
  215.  
  216.  
  217.  
  218.  
  219.  
  220. /****************************/
  221. /*  Function ReadLengths() */
  222. /****************************/
  223.  
  224. static void ReadLengths(tree)
  225. sf_tree *tree;
  226. {
  227.     int treeBytes;
  228.     int i;
  229.     int num, len;
  230.  
  231.     /* get number of bytes in compressed tree */
  232.     READBIT(8, treeBytes);
  233.     treeBytes++;
  234.     i = 0;
  235.  
  236.     tree->MaxLength = 0;
  237.  
  238. /* High 4 bits: Number of values at this bit length + 1. (1 - 16)
  239.  * Low  4 bits: Bit Length needed to represent value + 1. (1 - 16)
  240.  */
  241.     while (treeBytes > 0) {
  242.         READBIT(4, len);
  243.         len++;
  244.         READBIT(4, num);
  245.         num++;
  246.  
  247.         while (num > 0) {
  248.             if (len > tree->MaxLength)
  249.                 tree->MaxLength = len;
  250.             tree->entry[i].BitLength = len;
  251.             tree->entry[i].Value = i;
  252.             i++;
  253.             num--;
  254.         }
  255.  
  256.         treeBytes--;
  257.     }
  258. }
  259.  
  260.  
  261.  
  262.  
  263.  
  264. /****************************/
  265. /*  Function SortLengths() */
  266. /****************************/
  267.  
  268. static void SortLengths(tree)
  269. sf_tree *tree;
  270.  /* Sort the Bit Lengths in ascending order, while retaining the order
  271.    of the original lengths stored in the file */
  272. {
  273.     register sf_entry *ejm1;    /* entry[j - 1] */
  274.     register int j;
  275.     register sf_entry *entry;
  276.     register int i;
  277.     sf_entry tmp;
  278.     int entries;
  279.     unsigned a, b;
  280.  
  281.     entry = &tree->entry[0];
  282.     entries = tree->entries;
  283.  
  284.     for (i = 0; ++i < entries;) {
  285.         tmp = entry[i];
  286.         b = tmp.BitLength;
  287.         j = i;
  288.         while ((j > 0)
  289.                && ((a = (ejm1 = &entry[j - 1])->BitLength) >= b)) {
  290.             if ((a == b) && (ejm1->Value <= tmp.Value))
  291.                 break;
  292.             *(ejm1 + 1) = *ejm1;/* entry[j] = entry[j - 1] */
  293.             --j;
  294.         }
  295.         entry[j] = tmp;
  296.     }
  297. }
  298.  
  299.  
  300.  
  301.  
  302.  
  303. /******************************/
  304. /*  Function GenerateTrees() */
  305. /******************************/
  306.  
  307. static void GenerateTrees(tree, nodes)
  308. sf_tree *tree;
  309. sf_node *nodes;
  310.  /* Generate the Shannon-Fano trees */
  311. {
  312.     int codelen, i, j, lvlstart, next, parents;
  313.  
  314.     i = tree->entries - 1;      /* either 255 or 63 */
  315.     lvlstart = next = 1;
  316.  
  317.     /* believe it or not, there may be a 1-bit code */
  318.  
  319.     for (codelen = tree->MaxLength; codelen >= 1; --codelen) {
  320.  
  321.         /* create leaf nodes at level <codelen> */
  322.  
  323.         while ((i >= 0) && (tree->entry[i].BitLength == codelen)) {
  324.             nodes[next].left = 0;
  325.             nodes[next].right = tree->entry[i].Value;
  326.             ++next;
  327.             --i;
  328.         }
  329.  
  330.         /* create parent nodes for all nodes at level <codelen>,
  331.            but don't create the root node here */
  332.  
  333.         parents = next;
  334.         if (codelen > 1) {
  335.             for (j = lvlstart; j <= parents - 2; j += 2) {
  336.                 nodes[next].left = j;
  337.                 nodes[next].right = j + 1;
  338.                 ++next;
  339.             }
  340.         }
  341.         lvlstart = parents;
  342.     }
  343.  
  344.     /* create root node */
  345.  
  346.     nodes[0].left = next - 2;
  347.     nodes[0].right = next - 1;
  348. }
  349.  
  350.  
  351.  
  352.  
  353.  
  354. /************************/
  355. /*  Function ReadTree() */
  356. /************************/
  357.  
  358. #ifndef ASM
  359.  
  360. static void ReadTree(nodes, dest)
  361. register sf_node *nodes;
  362. int *dest;
  363.  /* read next byte using a shannon-fano tree */
  364. {
  365.     register int cur;
  366.     register int left;
  367.     UWORD b;
  368.  
  369.     for (cur = 0;;) {
  370.         if ((left = nodes[cur].left) == 0) {
  371.             *dest = nodes[cur].right;
  372.             return;
  373.         }
  374.         READBIT(1, b);
  375.         cur = (b ? nodes[cur].right : left);
  376.     }
  377. }
  378.  
  379. #endif                          /* !ASM */
  380.